package everydayGrade.t2;

import CommonStructure.ListNode;

/**
 * @Author: Siantar
 * @Date: 2023-07-31-23:07
 * @Description: 1.0
 */
public class T0143 {
    public void reorderList(ListNode head) {
        if (head==null)return;
        ListNode mid=findMid(head);
        ListNode l1=head;
        ListNode l2=mid.next;
        mid.next=null;
        l2=reverse(l2);
        ListNode l=merge(l1,l2);
    }

    public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode t = curr.next;
            curr.next = pre;
            pre = curr;
            curr = t;
        }
        return pre;
    }
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode res=l1;
        ListNode l1t,l2t;
        while (l2!=null){
            l1t=l1.next;
            l2t=l2.next;
            l1.next=l2;
            l1=l1t;
            l2.next=l1;
            l2=l2t;
        }
        return res;
    }
}
